AGC 015 题解

imily's notebook

2020-07-27

比赛

AB均为水题

C

网格图常见套路：C = V - E + F，前缀和，处理一下临界的行和列

一般的位运算题都是一位一位分开来搞，但这题没法这么做。

整体考虑。首先 A 和 B 前面相同的位可以忽略。

设第一个不同的位为 p，我们将区间划分为 $[A, 2^p)$ 和 $[2^p, B]$。

单取 $[A, 2^p)$，可以 or 出 $[A, 2^p)$

单取 $[2^p, B]$，设 B 中除 p 以外的最高位为 d，可以 or 出 $[2^p, 2^{d + 1})$

两个区间都取，可以 or 出 $[2^p + A, 2^{p + 1})$

答案就是这三个区间的并集。

看染了点 i 能染哪些点 j：

可以将 v 升序排列，设 li 表示最左的 xj >= xi 的 j，ri 表示最右的 xj <= xi 的 j。那么 i 能染到的区间就是 [li, ri]（这个区间中有些点是被 li 和 ri 染到的）

问题就转化成：给你若干个区间 [li, ri] 满足 li、ri 递增，求有多少种区间集合能覆盖所有的点？

dp，f[i] 表示选第 i 区间，覆盖 [1, ri] 的方案数，显然当 j < i 且 Rj >= li - 1 时 f[j] 可以转移到 f[i]

若 f[j] 能转移到 f[i]，则 f[j + 1] 也能转移到 f[i]，所以设 L 为最左边的 j, [L, i - 1] 的都能转移到 f[i]。容易发现 L 是单调递增的，维护 L 和前缀和就可以做了！

结论题，不是很懂（据说官方题解挂掉了？

逆推一波想到斐波那契数列，这很优的样子